package algorithm.recursionAndbacktrack.permuation.p47;

import java.util.*;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 */
class Solution_v1 {
    private Set<List<Integer>> permuations;
    private boolean[] visited;
    public List<List<Integer>> permuteUnique(int[] nums) {
        permuations = new HashSet<>();
        visited = new boolean[nums.length];
        if (nums != null && nums.length > 0) {
            permuteUnique(nums, new LinkedList<>());
        }
        return new ArrayList<>(permuations);
    }

    private void permuteUnique(int[] nums, LinkedList<Integer> permuation) {
        if (permuation.size() == nums.length) {
            permuations.add(new ArrayList<>(permuation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                permuation.add(nums[i]);
                permuteUnique(nums, permuation);
                permuation.removeLast();
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution_v1().permuteUnique(new int[]{1, 1, 2}));
    }
}